融合决策树的分布式多工厂协同生产调度方法

doi:10.16182/j.issn1004731x.joss. 19-0559

摘要/Abstract

摘要： 在分布式多工厂协同生产调度优化问题中,需同时考虑工件在工厂间柔性分配与工件在工厂内柔性调度2个阶段的优化。建立以制造总成本与提前/延期为优化目标的分布式多工厂调度模型,提出一种融合ID3决策树的高斯粒子群优化嵌套寻优算法框架。该框架将各工厂内部独立的调度优化嵌套于工厂间分配寻优过程,并引入精英保留策略提高算法寻优性,将ID3决策树技术融入外层寻优粒子生成过程来降低外层寻优的随机性。通过仿真验证算法在寻优性、收敛性和CPU时间方面的优越性。

关键词: 分布式多工厂, ID3决策树, 多目标粒子群优化, 精英保留策略

Abstract: In the synergic production scheduling optimization problem of distributed multi-plants, it is necessary to consider the two stages of job allocation between factories and job scheduling in factories at the same time. This paper first establishes a distributed multi-plant scheduling model with total cost and advance/delay as the optimization objectives, and then proposes a nested optimization algorithm framework integrating ID3 decision tree with Gauss particle swarm optimization. In this framework, independent scheduling optimization within the factory is nested in the process of inter factory allocation optimization, and elite retention strategy is introduced to improve the algorithm optimization. In addition, ID3 decision tree technology is integrated into the process of outer layer optimization particle generation to reduce the randomness of outer layer optimization. Simulation results show that the algorithm has advantages in optimization, convergence and CPU time.

Key words: Distributed multi-plants, ID3 decision tree, Multi-objective particle swarm optimization, Elite retention strategy

中图分类号:

TP18

王艳, 蒋天伦. 融合决策树的分布式多工厂协同生产调度方法[J]. 系统仿真学报, 2019, 31(11): 2181-2197.

Wang Yan, Jiang Tianlun. Synergic Production Scheduling Method for Distributed Multi-Plants Based on Fusion Decision Tree[J]. Journal of System Simulation, 2019, 31(11): 2181-2197.

参考文献

[1] Durão L, Christ A, Zancul E.Additive manufacturing scenarios for distributed production of spare parts[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2017, 93(2): 869-880.
[2] Bi Z, Xu L, Wang C.Internet of things for enterprise systems of modern Manufacturing[J]. IEEE Transactions on Industrial Informatics (S1551-3203), 2014, 10(2): 1537-1546.
[3] Behnamian J, Uhomi S.A survey of mufti-factory scheduling[J]. Journal of Intelligent Manufacturing (S0956-5515), 2016, 27(1): 231-249.
[4] 王凌, 邓瑾, 王圣尧. 分布式车间调度优化算法研究综述[J]. 控制与决策, 2016, 31(1): 1-11.
Wang Ling, Deng Jin, Wang Shengyao.Overview of distributed job shop scheduling optimization algorithms[J]. Control and Decision, 2016, 31(1): 1-11.
[5] Behnamian J, Ghomi S.The heterogeneous multi-factory production network scheduling with adaptive communication policy and parallel machine[J]. Information Sciences (S0020-0255), 2013, 219(10): 181-196.
[6] Khedr A M, Walid O.Minimum perimeter coverage of query regions in a heterogeneous wireless sensor network[J]. Information Sciences (S0020-0255), 2011, 181(15): 3130-3142.
[7] Zhang X, Cheung W, Li C.Learning latent variable models from distributed and abstracted data[J]. Information Sciences (S0020-0255), 2011, 181(14): 2964-2988.
[8] Mohsen Ziaee.Heuristic algorithm for the distributed and flexible job-shop scheduling problem[J]. Journal of Supercomputing (S0920-8542), 2014, 67(1): 69-83.
[9] Chan F, Chung S, Chan P L.An adaptive genetic algorithm with dominated genes for distributed scheduling problems[J]. Expert Systems with Applications (S0957-4174), 2005, 29(2): 364-371.
[10] Jia H Z, Nee A Y C, Fuh J Y H, et al. A modified genetic algorithm for distributed scheduling problems[J]. Journal of Intelligent Manufacturing (S0956-5515), 2003, 14(3): 351-362.
[11] Lu P, Wu M, Tan H, et al.A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems[J]. Journal of Intelligent Manufacturing (S0956-5515), 2018, 29(1): 19-34.
[12] Naderi B, Azab A.An improved model and novel simulated annealing for distributed job shop problems[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2015, 81(4): 693-703.
[13] Chang H, Liu T.Optimization of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J]. Journal of Intelligent Manufacturing (S0956-5515), 2017, 28(8): 1973-1986.
[14] Rutkowski L, Jaworski M, Pietruczuk L, et al.Decision trees for mining data streams based on the gaussian approximation[J]. IEEE Transactions on Knowledge & Data Engineering (S1041-4347), 2014, 26(1): 108-119.
[15] 齐战胜, 高峰, 腾达. 数据挖掘技术在计算机取证中的应用研究[J]. 信息网络安全, 2011, 11(9):163-166.
Qi Zhansheng, Gao Feng, Teng Da.Application of data mining technology in computer forensics[J]. Information Network Security, 2011, 11(9): 163-166.
[16] 张宇, 包研科, 邵良杉, 等. 面向分布式数据流大数据分类的多变量决策树[J]. 自动化学报, 2018, 44(6): 1115-1127.
Zhang Yu, Bao Yanke, Shao Liangshan, et al.Multivariate decision tree for large data classification of distributed data stream[J]. Journal of Automation, 2018, 44(6): 1115-1127.
[17] 崔琪, 吴秀丽, 余建军. 变邻域改进遗传算法求解混合流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(9): 1917-1927.
Cui Qi, Wu Xiuli, Yu Jianjun.Improved genetic algorithm variable neighborhood search for solving hybrid flow shop scheduling problem[J]. Computer Integrated Manufacturing System, 2017, 23(9): 1917-1927.
[18] Jamrus T, Chien C, Gen M, et al.Hybrid particle swarm optimization combined with genetic operators for flexible job-shop scheduling under uncertain processing time for semiconductor manufacturing[J]. IEEE Transactions on Semiconductor Manufacturing (S0894-6507), 2017, 31(1): 32-41.
[19] Zuo X, Zhang G, Wei T.Self-adaptive learning PSO-based deadline constrained task scheduling for hybrid IaaS Cloud[J]. IEEE Transactions on Automation Science & Engineering (S1545-5955), 2014, 11(2): 564-573.
[20] Gong Y, Li J, Zhou Y, et al.Genetic learning particle swarm optimization[J]. IEEE Transactions on Cybernetics (S2168-2267), 2017, 46(10): 2277-2290.
[21] Bao Y, Xiong T, Hu Z.PSO-MISMO modeling strategy for multistep-ahead time series prediction[J]. IEEE Transactions on Cybernetics (S2168-2267), 2014, 44(5): 655-668.
[22] 李飞, 刘建昌, 石怀涛, 等. 基于分解和差分进化的多目标粒子群优化算法[J]. 控制与决策, 2017, 32(3): 403-410.
Li Fei, Liu Jianchang, Shi Huaitao, et al.Multi-objective particle swarm optimization algorithm based on decomposition and differential evolution[J]. Control and Decision-making, 2017, 32(3): 403-410.
[23] 彭传勇. 广义粒子群优化算法及其在作业车间调度中的应用研究[D]. 武汉: 华中科技大学, 2006: 13-14.
Peng Chuanyong.Generalized particle swarm optimization and its application in job shop scheduling [D]. Wuhan: Huazhong University of Science and Technology, 2006: 13-14.
[24] 朱德刚, 孙辉, 赵嘉, 等. 基于高斯扰动的粒子群优化算法[J]. 计算机应用, 2014, 34(3): 754-759.
Zhu Degang, Sun Hui, Zhao Jia, et al.Particle swarm optimization algorithm based on Gauss perturbation[J]. Computer Applications, 2014, 34(3): 754-759.
[25] 苏兆品, 张国富, 蒋建国, 等. 基于非支配排序差异演化的应急资源多目标分配算法[J]. 自动化学报, 2017, 43(2): 195-214.
Su Zhaopin, Zhang Guofu, Jiang Jianguo, et al.Emergency resource multi-objective allocation algorithm based on differential evolution of non-dominated ranking[J]. Journal of Automation, 2017, 43(2): 195-214.
[26] 高亮, 张国辉, 王晓娟. 柔性作业车间调度智能算法及其应用[M]. 武汉: 华中科技大学出版社, 2012: 92-93.
Gao Liang, Zhang Guohui, Wang Xiaojuan.Flexible job shop scheduling intelligent algorithms and their applications [M]. Wuhan: Huazhong University of Science and Technology Press, 2012: 92-93.
[27] Brandimarte P.Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research (S0254-5330), 1993, 41(3): 157-183.
[28] Huang S, Tian N, Wang Y, et al.Multi-objective flexible job-shop scheduling problem using modified discrete particle swarm optimization[J]. Springer Plus (S2193-1801), 2016, 5(1): 1432-1454.
[29] Wang L, Zhou G, Xu Y, et al.An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job-shop scheduling[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2012, 60(9): 1111-1123.
[30] Zitzler E, Thiele L.Multi-objective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 1999, 3(4): 257-271.
[31] Ahmad N, Hossen J, Ali S M.Improvement of overall equipment efficiency of ring frame through total productive maintenance: a textile case[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2018, 94(1): 239-256.